package com.leetcode.根据数据结构分类.堆;

import com.sourcetrip.my.BinaryHeapV0;

import java.util.Arrays;

/**
 * @author: ZhouBert
 * @date: 2020/12/25
 * @description: 面试题 17.14. 最小K个数
 * https://leetcode-cn.com/problems/smallest-k-lcci/
 * 设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。
 */
public class B_面试题_17_14_最小K个数 {

	/**
	 * 由于已经写过一个大顶堆，那么直接使用大顶堆来进行题解。
	 * 分析：
	 * 1.利用大顶堆，将 k 个元素加入大顶堆；
	 * 2.将后续元素与堆顶元素进行比较，如果比堆顶元素小，进行替换(replace)，直至数组中的元素添加完毕。
	 * --
	 * 样例测试通过
	 * 看了下Java 中似乎没有实现 heap 的结构，如果用大顶堆来实现的话就会挺麻烦的。
	 * 看了下参考答案，似乎有用快排来解决。
	 * 等看到第二季的时候好好斟酌一下。
	 * @param arr
	 * @param k
	 * @return
	 */
	public static int[] smallestK(int[] arr, int k) {
		if (arr == null || k == 0 || arr.length == 0) {
			return new int[0];
		}
		if (k >= arr.length) {
			return arr;
		}

		BinaryHeapV0<Integer> heap = new BinaryHeapV0<>();
		for (int i = 0; i < k; i++) {
			heap.add(arr[i]);
		}
		//此时准备工作已经就绪
		for (int i = k; i < arr.length; i++) {
			if (arr[i] < heap.get()) {
				heap.replace(arr[i]);
			}
		}

		int[] res = new int[k];
		for (int i = 0; i < k; i++) {
			res[i] = heap.remove();
		}
		return res;
	}

	public static void main(String[] args) {
		int[] arr = {1, 3, 5, 7, 2, 4, 6, 8};
		int k=4;
		int[] res = smallestK(arr, k);
		System.out.println("res = " + Arrays.toString(res));

	}


}
